// 给定一个整型数组arr，和一个整数num，arr中的子数组sub
// 如果想达标，必须满足：sub中的最大值-sub中的最小值<=num
// 返回arr中达标子数组的数量
#include "../util/util.h"
#include <iostream>
#include <deque>
using namespace std;
int getNum(const int *arr, int arrLength,int num)
{
    deque<int> qmax;
    // 存放滑动窗口内最小值在数组内的下标
    deque<int> qmin;
    // 存放数组内满足条件的子数组数量
    int res = 0;
    // 滑动窗口左边界
    int L = 0;
    // 滑动窗口右边界
    int R = 0;
    while (L < arrLength)
    {
        for (R; R < arrLength; R++)
        {
            // qmax不为空，且尾元素下标R，arr[R]小于窗口新进来的元素
            while (!qmax.empty() && arr[qmax.back()] <= arr[R])
            {
                qmax.pop_back();
            }
            qmax.push_back(R);
            while (!qmin.empty() && arr[qmin.back()] >= arr[R])
            {
                qmin.pop_back();
            }
            qmin.push_back(R);
            // 不满足条件，停止，计算其子数组数量
            if (arr[qmax.front()] - arr[qmin.front()] > num)
            {
                break;
            }
        }
        //在这里R是第一个不满足的元素的下标，所以计算时，要给R-1
        res += R - L;
        // 判断滑动窗口左边界右移后，被移出窗口的元素是否是最大值或最小值
        if (arr[L] == arr[qmax.front()])
        {
            qmax.pop_front();
        }
        if (arr[L] == arr[qmin.front()])
        {
            qmin.pop_front();
        }
        L++;
    }
    return res;
}
int main()
{
    int arr[1024] = {0};
    int arrLength = 0;
    cout << "请输入数组的值" << endl;
    arrLength = Util::GetInstance().getArrFromStdin(arr);
    int num = 0;
    cout << "请输入num" << endl;
    cin >> num;
    int res = getNum(arr,arrLength,num);
    cout<<res<<endl;
    return 0;
}